//
// Created by xumy on 2021/9/9.
// 工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，然后将元素
//
#include "iostream"

using namespace std;

void insert_sort(int arr[], int len) {

    int i, j, temp;

    for (i = 1; i < len; ++i) {
        // 暂存待插入元素
        temp = arr[i];
        // 反复将代插入元素与前面已排好序的元素比较大小，若有比temp大的元素，则将其后挪，直到没有没有比temp大（所以是稳定的），或者开头为止
        for (j = i; j > 0 && arr[j-1] > temp; j--) {
            arr[j] = arr[j-1];
        }
        arr[j] = temp;
    }
}

int main() {

    int arrs[] = {3, 24, 5, 78, -1, 2304, 8, 1};
    int leng = sizeof(arrs) / sizeof(arrs[0]);

    // 排序前
    cout << "before: ";
    for (int i = 0; i < leng; ++i) {
        cout << arrs[i] << " ";
    }
    cout << endl;

    insert_sort(arrs, leng);

    // 排序后
    cout << "after: ";
    for (int i = 0; i < leng; ++i) {
        cout << arrs[i] << " ";
    }

    return 0;
}
